1. Field of the Invention
The present invention relates to a multiplier which can attain a high speed multiplication operation on the basis of a relatively simple circuit configuration.
2. Description of the Prior Art
Multipliers can be classified into roughly two, parallel and series, multipliers. In the series multiplier, the product of a multiplicand and a multiplier can be obtained in such a way that a multiplicand is multiplied by a multiplier digit by digit, the multiplication processing for each digit is shifted in sequence, and the multiplied results of all digits are accumulatively added.
More specifically, in the series multiplier, a partial product is formed by multiplying a multiplicand by a multiplier digit by digit, that is, bit by bit in a binary computer. For instance, in the case where the numbers of bits of a multiplier and a multiplicand are both 32 bits (32 bits.times.32 bits), the product can be obtained by forming 32 partial products of a 32-bit multiplicand and a one-bit multiplier and by accumulatively adding these 32 partial products. In the series multiplier, each partial product is formed for each digit of the multiplier in sequence and then accumulatively added in sequence in the order of the partial product formation. Therefore, one partial product forming circuit for forming many partial products and one adder circuit for sequentially and accumulatively adding these partial products are required. However, the calculation speed is slow.
In contrast with this, in the parallel multiplier, each partial product of a multiplicand and a multiplier is formed simultaneously for each digit, and all the partial products formed simultaneously are added also simultaneously, so that the calculation speed is very high. However, since all the partial products are formed and added simultaneously, in the case of a 32-bit multiplication, for instance, 32 partial product forming circuits and 32 adders for adding 32 partial products are necessary.
In addition, Booth's algorithm method is known as a method of multiplying a multiplicand by a multiplier in series and parallel fashion. In the series multiplier, multiplication is processed for each bit of a multiplier to form 32 partial products, for instance. In contrast with this, in this Booth method, partial products are formed every three bits of a multiplier and further one bit of these three bits is overlapped upon one of other adjacent three bits. As a result, in the case of 32 bit multiplication, only 16 partial products are formed. The 16 partial products are added to obtain a multiplied result. In this Booth method, since 16 partial products are formed in sequence every 3 bits of the multiplicand and then these partial products are added in sequence, only one partial product forming circuit and one adder are required as in the series multiplier, and advantageously the calculation speed thereof is two times higher than that of the series multiplier.
As explained above, although the series multiplier is simple and economical from the standpoint of circuit configuration, there exists a problem in that the calculation speed is very slow. Although the parallel multiplier is high in speed, there exists a problem in that many partial product forming circuits and adders are required, so that the cost is high and the space occupied by the circuit is voluminous. Further, in the Booth's algorithm multiplier belonging to between series and parallel circuits, although the speed is relatively high in spite of a relatively simple circuit configuration, the calculation speed is still slow as compared with that of the parallel multiplier. For instance, although the parallel multiplier can form and add partial products simultaneously, in the Booth method, 16 processing steps are required to process a multiplication of 32 bits, and therefore there still exists a problem in that the multiplication speed is 16 times slower than that of the parallel multipliers.